package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 买卖股票的最佳时机 II
 * @date 2025/5/29 14:27
 */
public class MaxProfit_122 {

    public static void main(String[] args) {
        MaxProfit_122 maxProfit122 = new MaxProfit_122();

        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit122.maxProfit(prices));
    }

    /**
     * 个解：dp-二维数组
     * <p>
     * 思路：前一天没股票，当天才能买入！！！（题目给出不能同时参与多笔交易）
     * 1.为什么对于第i天 持有 股票下的i-1天未持有，i天才买入的情况，这里和股票1的处理不一样（股票1： dp[i][1] = -prices[i]；而股票2：dp[i][1] = dp[i-1][0] - prices[i]）？
     * ——因为股票1，只买卖股票一次，所以当第i天才买入股票，那么第i天的利润当然只能是 -prices[i]，即购买股票的价格。
     * 然而股票2可以多次买卖，【当第i天买入股票时，前面可能已经买卖过股票（已经产生了利润）】，那么第i天买入的利润是-prices[i]；
     * 所以，此时的总利润还要加上前面买卖产生的利润，就是dp[i-1][0] - prices[i]。
     * <p>
     * 2.为什么这里dp[i][0]、dp[i][1]可以得到多次买卖的最大利润？？？
     * ——关键点在于：转移过程（dp数组递推公式）自动囊括了所有可能的买卖情况，每次做出的是当前最优选择。
     * 解释：
     * 在任何一天，都可以选择：
     *  不买不卖，继续保持；
     *  买入或卖出（只在合法状态转移下）；
     * 这个状态转移在循环中已经考虑到了 每一天的最优选择，即局部最优 => 全局最优。
     * 而多次买卖，本质就是：
     *  在所有上升的波段中买入再卖出，这已经通过状态转移中的 dp[i-1][1] + prices[i] 自动实现了。
     * 所以：
     *  如果最后一天没有股票，利润是 dp[n-1][0]；
     *  如果最后一天还持有股票，可能是为了前面一次更好的买卖时机提前买的，也可能没来得及卖，这时就要比较一下 dp[n-1][1] 是否更高。
     * 当然，一般来说 dp[n-1][0] 更大，因为卖掉股票后才是实际收益，但为了通用性和鲁棒性，我们保留 Math.max(...)。
     * <p>
     * T(n) = O(n)
     * S(n) = O(1)
     */
    public int maxProfit(int[] prices) {
        // 1.定义dp数组
        // 第 i 天持有，或未持有股票的最大利润（0-未持有，1-已持有）
        // dp[i][0]第i天 未持有 股票的最大利润（第i-1天未持有，或者第i天才卖出）
        // dp[i][1]第i天 持有 股票的最大利润（第i-1天已持有，或者第i天才买入）
        int[][] dp = new int[prices.length][2];

        // 2.递推公式
        // 1）第i天 未持有，dp[i][0]
        // i-1天未持有，dp[i-1][0]
        // i-1天持有，i天卖出，dp[i-1][1] + prices[i]
        // 2）第i天 持有，dp[i][1]
        // i-1天持有，dp[i-1][1]
        // i-1天未持有，i天才买入，dp[i-1][0] - prices[i]

        // 3.初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        String isHave = "";
        // 4.遍历
        // 从前往后
        for (int i = 1; i < prices.length; i++) {
            // 第i天未持有
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 第i天持有
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

            // 5.打印日志
            if (dp[i][0] > dp[i][1]) {
                isHave = "【未持有】";
                if (dp[i - 1][0] > dp[i - 1][1] + prices[i]) {
                    System.out.println("第" + i + "天" + isHave + "第" + (i - 1) + "天未持有" + "，dp[" + i + "][0] = " + "dp[" + (i - 1) + "][0]=" + dp[i - 1][0]);

                } else {
                    System.out.println("第" + i + "天" + isHave + "第" + (i - 1) + "天持有，第" + i + "天【卖出】" + "，dp[" + i + "][0] = " + "dp[" + (i - 1) + "][1]+prices[" + i + "]=" + (dp[i - 1][1] + prices[i]));
                }
            } else {
                isHave = "【持有】";
                if (dp[i - 1][1] > dp[i - 1][0] - prices[i]) {
                    System.out.println("第" + i + "天" + isHave + "第" + (i - 1) + "天持有" + "，dp[" + i + "][1] = " + "dp[" + (i - 1) + "][1]=" + dp[i - 1][1]);
                } else {
                    System.out.println("第" + i + "天" + isHave + "第" + (i - 1) + "天未持有，第" + i + "天【买入】" + "，dp[" + i + "][1] = " + "dp[" + (i - 1) + "][0]-prices[" + i + "]=" + (dp[i - 1][0] - prices[i]));
                }
            }

        }

        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);
    }

}
